1. Field of the Invention
The present invention relates to an error correction decoding apparatus and method, and more particularly, to a decoding apparatus and method which improve decoding performance by reducing a complexity when implementing a low density parity code (LDPC) decoding algorithm.
2. Description of the Related Art
A low density parity code (LDPC) encoding method is an error correction coding technique used in wireless communications and optical recording and/or reproducing fields. LDPC encoding includes a process to generate parity information (additional information) by using a parity check matrix in which the same number of elements whose values are 1 are included in each row and column, and the values of other elements are 0. That is, the parity information is determined to satisfy equation 1 below:H·C=0  (1)
Here, H denotes a p×c parity check matrix, and 0 is a zero matrix. C is a column matrix having elements of a c-bit codeword. The c-bit codeword includes an m-bit message word, k1, k2, . . . , km, and p-bit parity information, x1, x2, . . . , xp. Among the elements of the parity check matrix H and the column matrix C, the message word that is the object of encoding is already known and therefore, parity information xi (i=1, 2, . . . , p) can be determined using equation 1.
A detailed description of the LDPC encoding is disclosed in an article, “Good Error Correction Codes Based on Very Sparse Matrices” (D. J. MacKay, IEEE Trans. on Information Theory, vol. 45, No. 2, pp.399–431, 1999).
When a codeword having an error is LDPC encoded, which is transmitted through a channel and decoded, the parity check matrix that is used in the encoding is used for decoding. During the decoding, a great number of matrix computations are needed. Among the computations, there is a process in which one element in each row of the matrix is replaced by a value obtained by multiplying remaining element values in the same row excluding a value of the element. The multiplication increases complexity in implementing a system.
A technique has been suggested for an LDPC decoding algorithm without performing multiplications of matrix elements that increase system complexity. According to the technique, instead of multiplication operations, operations to replace the element of each row of the matrix with a minimum value among the element values of the row excluding the element value are performed and almost the same result could be obtained. A detailed description of this technique is described in an article, “Reduced Complexity of Iterative Decoding of Low Density Parity Check Codes Based on Belief Propagation” (M. Fossorier, M. Mihailjevic, and H. Imai, IEEE Trans. on Communications, vol. 47, No. 5, pp. 673–680,1999).
However, even in the technique of replacing the multiplication operations, the operation to obtain the minimum value among a plurality of the elements in each row should be repeated with a frequency corresponding to the number of elements of the matrix such that complexity increases.